/*
* Authors: Karymov Anton
*          Skorodumov Kirill
* Graph generator
* June-August,	2011
*/

#define BOOST_GRAPH_READ_GRAPHVIZ_ITERATORS
#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <ctime>
#include <iostream>

using namespace boost;
using namespace std;

// Vertex properties
typedef property <vertex_name_t, std::string,
  property <vertex_color_t, float > > vertex_p;  
// Edge properties
typedef property < edge_weight_t, double > edge_p;
// Graph properties
typedef property < graph_name_t, std::string > graph_p;
// adjacency_list-based type
typedef adjacency_list < vecS, vecS, undirectedS,
  vertex_p, edge_p, graph_p > graph_t;

//generates graph with given number of vertices and given maximal degree of a vertex
graph_t generate(unsigned int n, unsigned int max_deg) {
  int k;
  int p;

  srand(time(NULL));

  graph_t g(n);

  graph_traits<graph_t>::vertex_iterator i, iend;
  for (tie(i,iend) = vertices(g); i != iend; ++i) {
    int k = 1 + (rand() % max_deg);
    for (int j = degree(*i, g) + 1; j <= k; j++) {
      do {
        p = rand() % n;
      } while (edge(*i, p, g).second || (p == *i) || (degree(p, g) == max_deg));
      add_edge(*i, p, g);
    }
  }

  return g;
}

void main()
{
  // Construct an empty graph and prepare the dynamic_property_maps.
  graph_t g;
  dynamic_properties dp;

  property_map<graph_t, boost::vertex_name_t>::type name =
    get(vertex_name, g);
  dp.property("node_id",name);

  property_map<graph_t, boost::vertex_color_t>::type mass =
    get(vertex_color, g);
  dp.property("mass",mass);

  property_map<graph_t, boost::edge_weight_t>::type weight =
    get(edge_weight, g);
  dp.property("weight",weight);

  // Use ref_property_map to turn a graph property into a property map
  boost::ref_property_map<graph_t*,std::string> 
    gname(get_property(g,graph_name));
  dp.property("name",gname);

  unsigned int n;
  unsigned int k;

  cout << "Enter number of vertices in graph\n";
  cin >> n;
  cout << "Enter maximum degree of a vertex\n";
  cin >> k;

  g = generate(n, k);

  std::fstream ofile;
  ofile.open("output.dot",std::ios::out);		 
  write_graphviz(ofile, g);
  write_graphviz(std::cout, g);
  ofile.close();
}

